// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-03 16:45
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.Greedy;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

public class CanThreePartsEqualSum {
    /**
     * 判断给定数组是否可以连续划分为三等分
     */
    public boolean canThreePartsEqualSum(int[] arr) {
        // 每一个等分的都是总和的1/3
        int sum = Arrays.stream(arr).sum();
        if (sum == 0 && Arrays.stream(arr).distinct().count() == 1) {
            // 总和为0是一种特殊情况
            // 可以是元素全部为0，也可以使元素不全为0，或者不存在0
            // 元素中只有0
            return true;

        }
        int tPart = 0, k = 0;
        if (sum % 3 != 0) {
            // 数组总和不是3的倍数
            return false;
        } else {
            tPart = sum / 3;
        }
        int n = arr.length;

        int tmp = 0;
        for (int i = 0; i < n; i++) {
            // 数组中的0元素存在干扰
            if (arr[i] == 0 && tPart != 0) {
                continue;
            }
            tmp += arr[i];
            if (tmp == tPart) {
                tmp = 0;
                ++k;
            }
        }
        return k >= 3;
    }

    @Test
    public void shout00() {
        //int[] arr = {0, 2, 1, -6, 6, -7, 9, 1, 2, 0, 1};
        // int[] arr = {0, 0, 0, 0};
        // int[] arr = {1, -1, 1, -1, 1, -1};
        int[] arr = {10, -10, 10, -10, 10, -10, 10, -10};
        System.out.println(canThreePartsEqualSum(arr));
    }

}
